package com.xyz.study.algorithms;

import java.util.ArrayList;
import java.util.List;

/**
 * TODO
 *
 * @author XYZ
 * @version 1.0
 * @since 2021/4/25 18:42
 */
public class AlgorithmsDay20210425 {

    /**
     * Definition for a binary tree node.
     * public class TreeNode {
     * int val;
     * TreeNode left;
     * TreeNode right;
     * TreeNode() {}
     * TreeNode(int val) { this.val = val; }
     * TreeNode(int val, TreeNode left, TreeNode right) {
     * this.val = val;
     * this.left = left;
     * this.right = right;
     * }
     * }
     */
    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    /**
     * 方法一：中序遍历之后生成新的树
     * 算法
     *
     * 题目要求我们返回按照中序遍历的结果改造而成的、只有右节点的等价二叉搜索树。我们可以进行如下操作：
     *
     * 先对输入的二叉搜索树执行中序遍历，将结果保存到一个列表中；
     *
     * 然后根据列表中的节点值，创建等价的只含有右节点的二叉搜索树，其过程等价于根据节点值创建一个链表。
     *
     */
    class Solution1 {

        public TreeNode increasingBST(TreeNode root) {
            List<Integer> tempArray = new ArrayList<>();
            inorder(root, tempArray);
            TreeNode node = new TreeNode();
            TreeNode crrNode = node;
            for (int tempVal : tempArray){
                crrNode.right = new TreeNode(tempVal);
                crrNode = crrNode.right;
            }
            return node.right;
        }

        /**
         * 中序遍历
         * @param node
         * @param tempArray
         */
        public void inorder(TreeNode node, List<Integer> tempArray){
            if (node == null){
                return;
            }
            inorder(node.left, tempArray);
            tempArray.add(node.val);
            inorder(node.right, tempArray);
        }
    }

    /**
     * 方法二：在中序遍历的过程中改变节点指向
     * 方法一需要遍历一次二叉搜索树以后，然后再创建新的等价的二叉搜索树。事实上，还可以遍历一次输入二叉搜索树，在遍历的过程中改变节点指向以满足题目的要求。
     *
     * 在中序遍历的时候，修改节点指向就可以实现。具体地，当我们遍历到一个节点时，把它的左孩子设为空，并将其本身作为上一个遍历到的节点的右孩子。这里需要有一些想象能力。递归遍历的过程中，由于递归函数的调用栈保存了节点的引用，因此上述操作可以实现。下面的幻灯片展示了这样的过程。
     *
     */
    class Solution2 {
        private TreeNode lastNode;

        public TreeNode increasingBST(TreeNode root) {
            TreeNode tempNode = new TreeNode();
            lastNode = tempNode;
            inorder(root);
            return lastNode.right;
        }

        /**
         * 中序遍历
         * @param node
         */
        public void inorder(TreeNode node){
            if (node == null){
                return;
            }
            inorder(node.left);
            lastNode.right = node;
            node.left = null;
            lastNode = node;
            inorder(node.right);
        }
    }

}
